package pers.tz.题目.leetcode.数组;

import java.util.HashMap;
import java.util.Map;

import static pers.tz.common.ArrayUtils.*;

/**
 * 社招飞猪挂
 *
 * @author irony
 * @date 2024-03-09
 */
public class leetcode_0001_两数之和 {
// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
// 只会存在一个有效答案
// 输入：nums = [3,2,4], target = 6
// 输出：[1,2]

    public static void main(String[] args) {
        int[] ints = generateRandomArray(10, 1, 20);
        printArray(ints);

        int[] idxs1 = twoSum1(ints, 10);
        int[] idxs2 = twoSum2(ints, 10);
        printArray(idxs1);
        printArray(idxs2);
    }

    // 可行解
    private static int[] twoSum1(int[] ints, int sum) {
        for (int i = 0; i < ints.length; i++) {
            for (int j = i + 1; j < ints.length; j++) {
                if (ints[i] + ints[j] == sum) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[]{};
    }

    // 最优解
    private static int[] twoSum2(int[] ints, int sum) {
        // key：elementValue，key：elementIndex
        Map<Integer, Integer> hashMap = new HashMap<>(ints.length);
        for (int i = 0; i < ints.length; i++) {
            if (hashMap.containsKey(sum - ints[i])) {
                return new int[] {hashMap.get(sum - ints[i]), i};
            }

            hashMap.put(ints[i], i);
        }
        return new int[]{};
    }
}
